package hero.mps.leet_code_3;

import java.util.HashMap;
import java.util.Map;

public class SubStringWithoutDuplication {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int i = -1, res = 0, len = s.length();
        for(int j = 0; j < len; j++) {
            if (dic.containsKey(s.charAt(j)))
                i = Math.max(i, dic.get(s.charAt(j))); // 更新左指针 i
            dic.put(s.charAt(j), j); // 哈希表记录
            res = Math.max(res, j - i); // 更新结果
        }
        return res;
    }
    /**
     * 计算字符串s中不包含重复字符的最长子串的长度。
     *
     * @param s 给定的字符串
     * @return 字符串s中不包含重复字符的最长子串的长度
     */
    public int slideWindow(String s){
        int res = 0;
        Map<Character, Integer> memory = new HashMap<>();
        for(int i = 0, j = 0; i < s.length(); i++) {
            // 如果当前字符在memory中存在
            if (memory.containsKey(s.charAt(i))) {
                // 更新j的值为当前字符上一次出现的下标与j中的较大值
                j = Math.max(j, memory.get(s.charAt(i)));
            }
            // 更新res的值为当前窗口长度与res中的较大值
            res = Math.max(res, i - j +1);
            // 将当前字符及其下标+1存入memory中
            memory.put(s.charAt(i), i + 1);
        }
        return res;
    }
    /**
     * 使用暴力破解法寻找字符串s中最长无重复字符子串的长度
     *
     * @param s 待搜索的字符串
     * @return 返回最长无重复字符子串的长度
     */
    public int bruteForceAttack(String s) {
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            // 创建一个长度为300的布尔数组books，用于记录字符是否出现过
            boolean[] books = new boolean[128];
            // 从当前位置i开始向前遍历
            for (int j = i; j >=0; j--) {
                // 如果books数组中当前位置的字符已经出现过
                if (books[s.charAt(j)]) {
                    // 则跳出内层循环
                    break;
                }
                // 将books数组中当前位置的字符标记为已出现过
                books[s.charAt(j)] = true;
                // 更新最长无重复字符子串的长度
                res = Math.max(res, i - j + 1);
            }
        }
        // 返回最长无重复字符子串的长度
        return res;
    }
    public int lengthOfLongestSubstringDP(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int  res = 0, temp = 0, len = s.length();
        for(int j = 0; j < len; j++) {
            int i = dic.getOrDefault(s.charAt(j), -1);  // 获取索引i
            dic.put(s.charAt(j), j); //更新哈希表
            temp = temp < j - i ? temp + 1 : j - i; // dp[j-1] < j-i
            res = Math.max(res, temp); // max(dp[j-1], dp[j])
        }
        return res;
    }



    public static void main(String[] args) {
        SubStringWithoutDuplication subString = new SubStringWithoutDuplication();
        String str = "abcabcbb";
        System.out.println(subString.slideWindow(str));
    }

}
